package com.gitee.wsl.collections.deque.link

import com.gitee.wsl.collections.deque.Deque


/**
 * A linked list extension of the [Deque] interface where the link pointers are tightly
 * integrated with the element. Linked deques have no capacity restrictions; they grow as necessary
 * to support usage. They are not thread-safe; in the absence of external synchronization, they do
 * not support concurrent access by multiple threads. Null elements are prohibited.
 *
 *
 * Most `LinkedDeque` operations run in constant time by assuming that the element parameter
 * is associated with the deque instance. Any usage that violates this assumption will result in
 * non-deterministic behavior.
 *
 *
 * An element can exist in only one instance of a deque implementation, but may exist in multiple
 * implementations. Each implementation must define unique names for accessing and modifying its
 * link pointers.
 *
 *
 * The iterators returned by this class are *fail-fast*: If the deque is structurally modified
 * at any time after the iterator is created, in any way except through the iterator's own
 * [remove][Iterator.remove] method, then the iterator will throw a
 * [ConcurrentModificationException]. Thus, in the face of concurrent modification, the
 * iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at
 * an undetermined time in the future. Note that the fail-fast behavior of an iterator cannot be
 * guaranteed and should be used only to detect bugs.
 *
 * @author ben.manes@gmail.com (Ben Manes)
 * @param <E> the type of elements held in this collection
</E> */
interface LinkedDeque<E> : Deque<E> {
    /**
     * Returns if the element is at the front of the deque.
     *
     * @param e the linked element
     */
    fun isFirst(e: E): Boolean

    /**
     * Returns if the element is at the back of the deque.
     *
     * @param e the linked element
     */
    fun isLast(e: E): Boolean

    /**
     * Moves the element to the front of the deque so that it becomes the first element.
     *
     * @param e the linked element
     */
    fun moveToFront(e: E)

    /**
     * Moves the element to the back of the deque so that it becomes the last element.
     *
     * @param e the linked element
     */
    fun moveToBack(e: E)

    /**
     * Retrieves the previous element or `null` if either the element is unlinked or the first
     * element on the deque.
     */

    fun getPrevious(e: E): E?

    /** Sets the previous element or `null` if there is no link.  */
    fun setPrevious(e: E,  prev: E?)

    /**
     * Retrieves the next element or `null` if either the element is unlinked or the last
     * element on the deque.
     */
    fun getNext(e: E): E?

    /** Sets the next element or `null` if there is no link.  */
    fun setNext(e: E,  next: E?)

    override fun iterator(): MutableIterator<E>

    override fun descendingIterator(): MutableIterator<E>


    interface PeekingIterator<E> : MutableIterator<E> {
        /** Returns the next element in the iteration, without advancing the iteration.  */
        fun peek(): E

        override fun remove() {
            throw NotImplementedError("Not supported")
        }

        companion object {
            /** Returns an iterator that returns the first iteration followed by the second iteration.  */
            fun <E> concat(
                first: PeekingIterator<E>,
                second: PeekingIterator<E>,
            ): PeekingIterator<E> {
                return object : PeekingIterator<E> {
                    override fun hasNext(): Boolean {
                        return first.hasNext() || second.hasNext()
                    }

                    override fun next(): E {
                        if (first.hasNext()) {
                            return first.next()
                        } else if (second.hasNext()) {
                            return second.next()
                        }
                        throw NoSuchElementException()
                    }

                    override fun peek(): E {
                        return if (first.hasNext()) first.peek() else second.peek()
                    }
                }
            }

            /** Returns an iterator that selects the greater element from the backing iterators.  */
            fun <E> comparing(
                first: PeekingIterator<E>,
                second: PeekingIterator<E>,
                comparator: Comparator<E>,
            ): PeekingIterator<E> {
                return object : PeekingIterator<E> {
                    override fun hasNext(): Boolean {
                        return first.hasNext() || second.hasNext()
                    }

                    override fun next(): E {
                        if (!first.hasNext()) {
                            return second.next()
                        } else if (!second.hasNext()) {
                            return first.next()
                        }
                        val o1 = first.peek()
                        val o2 = second.peek()
                        val greaterOrEqual = (comparator.compare(o1, o2) >= 0)
                        return if (greaterOrEqual) first.next() else second.next()
                    }

                    override fun peek(): E {
                        if (!first.hasNext()) {
                            return second.peek()
                        } else if (!second.hasNext()) {
                            return first.peek()
                        }
                        val o1 = first.peek()
                        val o2 = second.peek()
                        val greaterOrEqual = (comparator.compare(o1, o2) >= 0)
                        return if (greaterOrEqual) first.peek() else second.peek()
                    }
                }
            }
        }
    }
}